package top;

import java.util.Arrays;

/**
 *
 * 计数质数
 *
 * @author chenyw
 * @date 2022/7/16 12:14
 */
public class Top204countPrimes {
/*    //枚举，会超时
    public int countPrimes(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean isPrime(int i) {
        int max = (int) Math.sqrt(i);
        for (int j = 2; j <= max; j++) {
            if (i % j == 0) {
                return false;
            }
        }
        return true;
    }*/

    //埃氏筛
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
                //不加这个判断可能i*i可能会超过整形，变成负数， 但满足j<n会进循环数组越界
                if ((long) i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
        }
        return count;
    }
}
